Search results for "finite language"
showing 4 items of 4 documents
Complexity of operations on cofinite languages
2010
International audience; We study the worst case complexity of regular operation on cofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.
The Average State Complexity of the Star of a Finite Set of Words Is Linear
2008
We prove that, for the uniform distribution over all sets Xof m(that is a fixed integer) non-empty words whose sum of lengths is n, $\mathcal{D}_X$, one of the usual deterministic automata recognizing X*, has on average $\mathcal{O}(n)$ states and that the average state complexity of X*is i¾?(n). We also show that the average time complexity of the computation of the automaton $\mathcal{D}_X$ is $\mathcal{O}(n\log n)$, when the alphabet is of size at least three.
On-line construction of a small automaton for a finite set of words
2009
In this paper we describe a ``light'' algorithm for the on-line construction of a small automaton recognising a finite set of words. The algorithm runs in linear time. We carried out good experimental results on the suffixes of a text, showing how this automaton is small. For the suffixes of a text, we propose a modified construction that leads to an even smaller automaton.
The average state complexity of rational operations on finite languages is linear
2010
Considering the uniform distribution on sets of m non-empty words whose sum of lengths is n, we establish that the average state complexities of the rational operations are asymptotically linear.